Задача #M103J

Память 32 MB Время 1000 ms Сложность 1 %

Statistika - 2

Sizga uzunligi \( n \) bo'lgan ikki \( X \) va \( Y \) ikkita massivlari beriladi. har bir ( \(x_i, y_i \) ) juftlik 2D fazodagi nuqtani ifodalaydi. Siz ikkita turdagi jami \( q \) ta so'rovlarni bajarishingiz kerak:

\( 1 \ i \ a \ b \) turidagi so'rov. Bu so'rov uchun \( (x_i, y_i) \) juftligi qiymatini \( (a, b) \) ga o'zgartiring.
\(2 \ l \ r\) turdagi so'rov. Bu so'rov uchun \( [l, r] \) oralig'idagi nuqtalarning nuqtalar o'zaro qanday bog'langanligini - korrelyatsiya koeffitsientini hisoblang.

Korrelyatsiya koeffitsienti quyidagi formula bilan hisoblanadi:

\( \overline{x} \) - oraliqdagi barcha \( x_i \) qiymatlarning o'rta arifmetik qiymati bo'lsin.

\( \overline{y} \) - oraliqdagi barcha \( y_i \) qiymatlarning o'rta arifmetik qiymati bo'lsin.

Unda korrelyatsiya koeffitsienti quyidagi formula orqali hisoblanadi:

Agar maxraj hamda surat nolga teng bo'lsa, korrelyatsiya koeffitsienti aniqlanmagan hisoblanadi. Bu holatda “undefined” deb chiqaring.

Agar surat musbat va maxraj nolga teng bo'lsa “inf” deb chiqaring.

Agar surat manfiy va maxraj nolga teng bo'lsa, “-inf” deb chiqaring.

Входные данные:

Birinchi qatorda ikkita butun son \( n \) va \( q \) berilgan, bunda:

Keyingi \( n \) qatorda ikkita butun son \( x_i \) va \( y_i \) berilgan, \( i \)-nuqtaning koordinatalarini ifodalaydi.

Keyingi \( q \) qatorda so'rovlar berilgan:
- Birinchi turdagi so'rov uchun qatorda `1 i a b` berilgan, bunda:
- \( i \) — yangilanadigan nuqtaning indeksi.
- \( a \) va \( b \) — yangi koordinatalar \( (x_i, y_i) \).
- Ikkinchi turdagi so'rov uchun qatorda `2 l r` berilgan, bunda:
- \( l \) va \( r \) — \( [l, r] \) oralig'ining indekslari.

Cheklovlar:

- \( 1 \leq n, q \leq 10^5 \)
- \( -25 \leq x_i, y_i \leq 25 \)
- \( 1 \leq i, l, r \leq n \)
- \( -25 \leq a, b \leq 25 \)

Выходные данные:

Har bir oraliq so'rovi uchun \( [l, r] \) oralig'idagi nuqtalarning korrelyatsiya koeffitsientini chiqaring:
- Agar korrelyatsiya koeffitsienti aniqlanmagan bo'lsa, `undefined` chiqaring.
- Agar korrelyatsiya koeffitsienti inf bo'lsa, `inf` chiqaring.
- Agar korrelyatsiya koeffitsienti -inf bo'lsa, `-inf` chiqaring.
- Aks holda, korrelyatsiya koeffitsientini chiqaring

Dasturingiz chiqargan son, juri yechimi chiqargan sondan ko'p bilan \( 10^{-4} \) farq qilishi lozim.

Примеры

#	input.txt	output.txt
1	5 5 1 2 3 4 5 6 7 8 9 10 2 1 5 1 3 10 20 2 1 5 2 2 4 2 1 3	1.00000000 0.88345221 0.93471954 0.99377021
2	3 4 -1 1 0 0 1 -1 2 1 3 1 2 5 5 2 1 3 2 2 3	-1.00000000 0.78571429 1.00000000
3	4 4 1 1 1 1 1 1 1 1 2 1 4 1 2 2 2 2 1 4 1 3 2 -2	undefined 1.00000000

input.txt

output.txt

-1.00000000
0.78571429
1.00000000

undefined
1.00000000

Примечание:

Birinchi test uchun izoh

1. Birinchi So'rov (`2 1 5`):

- Oraliq: \( [1, 5] \) (barcha 5 nuqta).
- Bu nuqtalar bir to'g'ri chiziqda joylashgan, shuning uchun korrelyatsiya koeffitsienti \( 1.00000000 \) ga teng.

2. Ikkinchi So'rov (`1 3 10 20`):
- Uchinchi nuqtani \( (5, 6) \) dan \( (10, 20) \) ga yagilanadi.
- Yangi nuqtalar: \( (1, 2), (3, 4), (10, 20), (7, 8), (9, 10) \).

3. Uchinchi So'rov (`2 1 5`):
- Oraliq: \( [1, 5] \) (barcha 5 nuqta).
- Nuqtalar: \( (1, 2), (3, 4), (10, 20), (7, 8), (9, 10) \).
- Uchinchi nuqta \( (10, 20) \) chiziqdan biroz chetga chiqqanligi sababli, korrelyatsiya koeffitsienti \( 0.99339927 \) ga teng.

4. To'rtinchi So'rov (`2 2 4`):
- Oraliq: \( [2, 4] \) (2-chi, 3-chi va 4-chi nuqtalar).
- Nuqtalar: \( (3, 4), (10, 20), (7, 8) \).
- Korrelyatsiya koeffitsienti: 0.93471954

5. Beshinchi So'rov (`2 1 3`):
- Oraliq: \( [1, 3] \) (1-chi, 2-chi va 3-chi nuqtalar).
- Nuqtalar: \( (1, 2), (3, 4), (10, 20) \).
- Korrelyatsiya koeffitsienti: 0.99377021

Telegram Facebook

Отправить решение

Пожалуйста, войдите в систему, чтобы выполнить это действие,если у вас нет учетной записи, вы можете зарегистрироваться в любое время